1. Field of the Invention
The present invention relates to protocols for creation of an ad hoc mobile network by multiple ad hoc mobile routers. The present invention also relates to management of the ad hoc mobile network by the multiple ad hoc mobile routers by distributing routing information and network traffic in an efficient manner.
2. Description of the Related Art
Mobile computing has evolved to an extent that it is no longer limited to a mobile computing model (e.g., “Mobile IP”) that relies a fixed wide area network infrastructure such as the Internet to provide connectivity between a mobile node and a correspondent node; rather, an ad hoc networking model has been pursued that enables an isolated group of mobile nodes to independently establish communications among each other (e.g., a “mesh”) and establish optimized routing paths among each other.
In particular, the aforementioned Mobile IP model has been developed based on numerous proposals by Internet Engineering Task Force (IETF) groups: these IETF proposals (e.g., Requests for Comments (RFCs), Internet Drafts, etc.) have addressed improved mobility support of Internet Protocol (IP) based mobile devices (e.g., laptops, IP phones, personal digital assistants, etc.) in an effort to provide continuous Internet Protocol (IP) based connectivity for IP devices to a fixed wide area network such as the Internet. These IETF proposals have described the Mobile IP model as relying on an IP node (IPv4 or IPv6) having a home address that is registered with a home agent at its home network: the home agent and home network are assumed to be fixed within the Internet architecture, enabling the home address to be globally reachable by any Internet node via the fixed home network and home agent.
If the IP node in the Mobile IP model is roaming away from its home network and establishes communications in a visited IP network, the visited IP network assigns a care-of address to the IP node: the care-of address is globally reachable in the Internet via a fixed gateway at the edge of the visited IP network (also referred to herein as a “visited gateway”). Since the visited gateway provides a fixed presence on the Internet for the visited IP network, registration by an IP node with its home agent (by specifying that the roaming IP node is reachable via the care-of address assigned by the visited IP network) enables the home agent to use the care-of address to forward packets destined for the home address to the IP node, for example via a tunnel between the home agent and the visited gateway. Alternately, the tunnel can be extended to the router nearest the roaming IP node based on the roaming IP node employing a reverse routing header as described in U.S. Patent Publication No. US 2004/0117339, published Jun. 17, 2004, the disclosure of which is incorporated in its entirety herein by reference.
Hence, an IPv4 or IPv6 node (host or router) in the Mobile IP model can seamlessly “roam” among different mobile IP networks, based on relying upon the home agent and visited gateway having a fixed presence on the Internet. Since the Internet utilizes a hierarchy of aggregate network addresses that enables scalability, the reliance of a fixed presence for the home agent and the visited gateway in the Internet enables similar optimization techniques to be applied in mobile IP networks relying on a fixed gateway, for example aggregation of network addresses and network prefixes based on a hierarchal network model. See, for example, U.S. Patent Publication No. US 2005/0099971, published May 12, 2005, the disclosure of which is incorporated in its entirety herein by reference.
In contrast, the ad hoc networking model assumes no previous existing network topology: Internet connectivity is neither assumed nor precluded, and every network node is assumed to be mobile. Consequently, the ad hoc networking model assumes no more that a group of mobile nodes (hosts and routers) may arbitrarily connect to each other via available link layer (“Layer 2”) connections, resulting in a mesh network. Hence, the ad hoc networking model addresses routing protocols that enable the ad hoc network nodes to create optimized network layer paths to each other, using for example a directed acyclic graph-based path or a tree topology-based path.
The IETF has a Mobile Ad-hoc Networks (MANET) Working Group that is working to implement this ad hoc networking model by developing standardized MANET routing specification(s) for adoption by the IETF. According to the MANET Working Group, the “mobile ad hoc network” (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links—the union of which form an arbitrary graph. The routers and hosts are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet.
The MANET system is particularly suited to low-power radio networks that may exhibit an unstable topology, where wireless propagation characteristics and signal quality between a wireless transmission source and a receiver can be difficult to model and quantify. Since there is no fixed network infrastructure in a MANET, the device address is tied to the device, not a topological location. As described in an Internet Draft by Baker, entitled “An Outsider's View of MANET” (Mar. 17, 2002), the fundamental behavior of a MANET is that a mobile router in a MANET retains a unique address prefix that may be distinct from the address prefixes of neighboring mobile routers; in other words, neighboring mobile routers in a MANET may have distinct address prefixes. Consequently, if a mobile router in a MANET moves, the movement causes a change in the routing infrastructure that requires recalculation of routes in accordance with the new topology. Hence, efficient routing algorithms are needed to ensure rapid convergence of the new topology based on the recalculated routes. One exemplary routing protocol is Open Shortest Path First (OSPF) (as specified by the IETF Request for Comments (RFC) 2178).
Communications between mobile routers of an ad hoc network can be optimized based on the mobile routes organizing into a tree-based topology. For example, U.S. Patent Publication No. US 2004/0032852, published Feb. 19, 2004, entitled “Arrangement for Router Attachments Between Roaming Mobile Routers in a Mobile Network”, the disclosure of which is incorporated in its entirety herein by reference, describes a technique for each mobile router of an mobile ad hoc network to independently select whether to attach to a candidate attachment router, based on tree information options advertised by the candidate attachment router and selection criteria employed by the mobile router. The independent selection by each router of whether to attach to another router enables the routers to dynamically establish a tree-based network topology model, where each router may continually determine whether an alternate attachment point within the tree is preferred.
Once a tree-based topology has been established within the ad hoc network, routing information can be distributed in an efficient manner. For example, U.S. Patent Publication No. US 2005/0265259, published Dec. 1, 2005 entitled “Arrangement for Providing Network Prefix Information from Attached Mobile Routers to a Clusterhead in a Tree-Based Ad Hoc Mobile Network”, the disclosure of which is incorporated in its entirety herein by reference, describes optimized transfer of routing information between mobile routers in an ad hoc mobile network having a tree topology, wherein the ad hoc network includes a single clusterhead and attached mobile routers. Each attached mobile router has a default egress interface configured for sending messages toward the clusterhead, and ingress interfaces configured for receiving messages from attached network nodes that are away from the clusterhead. A neighbor advertisement message received from an ingress interface away from a clusterhead is used by the attached mobile router to identify specified network prefixes that are reachable via the source of the neighbor advertisement message. The attached mobile router outputs on its default upstream interface a second neighbor advertisement message that specifies the network prefix used by the attached mobile router, and the specified network prefixes from the neighbor advertisement message received on the ingress interface. Hence, the propagation of neighbor advertisement messages toward the clusterhead establishes connectivity with minimal routing overhead.
The nature of ad hoc networking also enables individual tree-based ad hoc networks to form a larger ad hoc network based on neighboring border routers from the respective ad hoc networks communicating amongst each other, forming a bridge between the tree-based ad hoc networks. An example of individual tree-based ad hoc networks forming a larger ad hoc network using a bridge between respective border routers is described in U.S. Patent Publication No. US 2004/0081152, entitled “Arrangement for Router Attachments between Roaming Mobile Routers in a Clustered Network”, published Apr. 29, 2004, the disclosure of which is incorporated in its entirety herein by reference. Hence, ad hoc networks can join together to form even larger ad hoc networks.
As described above, a fundamental problem with the ad hoc networking model is that movement of a mobile router in the ad hoc network requires recalculation of routes for the new topology. However, the formation of a larger ad hoc network creates a greater probability that an individual mobile router will move, requiring route recalculation for each movement by a mobile router. Further, the formation of the larger ad hoc network requires recalculation of routes among a larger number of mobile routers, resulting in a longer convergence time. Consequently, the size of the ad hoc network is limited by the frequency of route recalculation relative to the convergence time, because if the frequency of route recalculation exceeds the convergence time, the ad hoc network will lose connectivity between the ad hoc mobile nodes due to their failure to converge before another ad hoc mobile node moves.
Even if a large ad hoc network manages to converge before another ad hoc mobile node moves, communications efficiency within the ad hoc network suffers dramatically due to substantially increased overhead in packets utilizing routing headers, since a separate routing header is required for each hop in the path from a source node to a destination node.
Consequently, a fundamental problem with a large ad hoc network is the associated increase in routing information that must be distributed to maintain network integrity (i.e., convergence of network routes) and to permit routing of packets.